Packet forwarding devices, such as layer 2 switches and layer 3 routers, utilize memory devices to store packets before they are sent to their intended destinations. In general, a packet forwarding device includes ports and a switch fabric for switching packets between ports. In a shared memory switch fabric architecture, a packet arrives at one port and is classified to an egress queue in the shared memory associated with the port to which the packet will be forwarded. A scheduler schedules packets to be dequeued and sent to the destination port using a scheduling algorithm. The scheduling algorithm may be based on any suitable criteria, such as first-in-first-out, quality of service, etc.
The memories used in packet forwarding devices are selected to meet the bandwidth requirements of the system. For example such memories must have access times that are at least on the order of line rates at which packets are sent to the packet forwarding devices. Due to current network bandwidth demands, packet forwarding devices typically high-speed static random access memories (SRAMs) for main packet memory.
One problem with using high-speed SRAMs for main memory in a packet forwarding device is that high-speed SRAMs are expensive when compared to other types of memory, such as dynamic random access memories (DRAMs). Thus, it may be desirable to use memory chips that have long burst lengths or slower random access times in order to reduce the cost of buffer memory in packet forwarding devices. The random access time of a memory is the minimum time period between which accesses to random memory locations can occur. The burst length of a memory refers to the minimum amount of data that can be written to or read from the memory during a single write or read cycle. Memories with longer burst lengths and slower random access times can be used to achieve the same bandwidth as faster SRAMs. However, inefficiencies can result. For example, one inefficiency that can result in operating a long burst length memory is that on the write side, packets may be smaller than the burst length of the memory. Thus, during a single write cycle, if a single packet is written to the memory, the packet may only use a portion of the burst length, thus making the write operation inefficient. Similarly, on the read side, if it is desirable to read a single packet from the memory and the packet size is less than the burst length of the memory, unneeded data will be read from the memory in order to extract the desired data.
While over-clocking a long burst length memory can be used to achieve a desired data rate. The memory may not be capable of operating at a sufficiently rapid rate if the burst length of the memory is much greater than the average packet size. For example, over-clocking may be used to achieve the desired data rate in instances in which the burst length is less than an order of magnitude greater than the average packet size. However, if the burst length is an order of magnitude or greater than the average packet size, over-clocking cannot be used to compensate for the inefficiency because the memory may not be fast enough to achieve the desired bandwidth.
One partial solution to these problems associated with using long burst length, slow random access time memories in packet forwarding devices is to use interleaving. That is, the packet memory can be organized in banks and packets may be alternatingly written to and read from the different banks of the memory. The random access time of a memory is typically faster if different banks of the memory are alternatingly accessed. While interleaving packets is possible on the write side, it is difficult to implement interleaving on the read side. For example, in a network switch, packets may be alternatingly written to different memory banks by a packet classifier. However, because packets are scheduled or dequeued based on criteria unrelated to memory banks, there is no guarantee that one packet will be read from a different memory bank than a previous packet. Thus, read operations from the packet memory will likely suffer the same underutilization inefficiency described above for the general case.
Accordingly, in light of these difficulties associated with conventional packet memories, there exists a need for methods and systems for caching packets to improve utilization of a packet memory.